from typing import List


# 377. 组合总和 Ⅳ
# 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
# 题目数据保证答案符合 32 位整数范围。
def combinationSum4(nums: List[int], target: int) -> int:
    nums.sort()

    # 记录每个数字的次数，避免超时
    num_dict = dict()

    # 使用回溯算法，会超时
    def back_track(current_index: int, count: int):
        if count == 0:
            return 1

        if count < 0:
            return 0

        # 查询字典，避免重复计算
        if count in num_dict:
            return num_dict[count]

        result_size = 0
        for start_index in range(current_index, len(nums)):
            num = nums[start_index]

            count -= num
            count_size = back_track(0, count)

            result_size = result_size + count_size

            count += num

        # 存储起来，避免超时
        num_dict[count] = result_size

        return result_size

    return back_track(0, target)


# 使用动态规划的方式
def combinationSum4_dp(nums: List[int], target: int) -> int:
    # dp[0] = 1
    # target 为 0，只有一种情况
    dp = [1] + [0] * target

    # 动态转移方程：当前位置 i 是所有 i-num 的累加和
    # dp[i] = for num in nums: dp[i-num]

    for index in range(1, target + 1):
        count = 0
        for num in nums:
            if index >= num:
                count += dp[index - num]
        dp[index] = count

    return dp[target]


nums_1 = [1, 2, 3]
target_1 = 4
result = combinationSum4(nums_1, target_1)
result_2 = combinationSum4_dp(nums_1, target_1)
print(f"result:{result} , compareWith_dp:{result == result_2}")

nums_1 = [9]
target_1 = 3
result = combinationSum4(nums_1, target_1)
result_2 = combinationSum4_dp(nums_1, target_1)
print(f"result:{result} , compareWith_dp:{result == result_2}")

nums_1 = [4, 2, 1]
target_1 = 32
result = combinationSum4(nums_1, target_1)
result_2 = combinationSum4_dp(nums_1, target_1)
print(f"result:{result} , compareWith_dp:{result == result_2}")
